package com.gwcloud.leetcode.offers;

/** 
* @ClassName   : Leetcode0420 
* @author      : ganwei 
* @date        : 2020年6月5日 
* @Description : TODO 
*/
public class Leetcode0420 {
	/**
	 * -动态规划，状态转移方程，但是解法超时
	 */
    public int maxSubArray(int[] nums) {
    	int len = nums.length;
    	int max = Integer.MIN_VALUE;
    	int[][] dp = new int[len][len];
    	
    	for(int i = 0; i < len; i++) {
    		dp[i][i] = nums[i];
    		max = Math.max(max, dp[i][i]);
    	}
    	
    	for(int i = 0; i < len; i++) {
    		for(int j = i+1; j < len; j++) {
    			dp[i][j] = dp[i][j-1] + dp[j][j];
    			max = Math.max(max, dp[i][j]);
    		}
    	}
    	
    	return max;
    }
    
    /**
     * -动态规划，不超时版
     */
    public int maxSubArray_1(int[] nums) {
    	int res = nums[0];
    	for(int i = 1; i < nums.length; i++) {
    		nums[i] += Math.max(nums[i-1], 0);
    		res = Math.max(res, nums[i]);
    	}
    	return res;
    }
}
